package com.zdp.algorithm.linkedlist;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 删除倒数第k个节点
 * @author Zhengdp
 * @date 2023年01月31日 16:02
 */
public class DelLastKthNode {
    public static void main(String[] args) throws IOException {
        DelLastKthNodeImpl1 impl = new DelLastKthNodeImpl1();
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = input.readLine().split(" ");
        String[] s2 = input.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int k = Integer.parseInt(s1[1]);
        Node head = Node.createNodeList(s2);
        head = impl.delLastKThNode(head,k);
        while(head != null) {
            System.out.println(head.value + " ");
            head = head.next;
        }
    }
}

/**
 * 快慢指针实现
 */
class DelLastKthNodeImpl1 {
    Node delLastKThNode(Node head,int k) {
        if(head.next == null || k <= 0 ) {
            return head.next;
        }
        Node fast = head;
        while(k != 0 && fast != null) {
            fast = fast.next;
            k--;
        }
        if(fast == null) {
            return head.next;
        }
        Node slow = head;
        while(fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return head.next;
    }
}

/**
 * 倒数第K个结点，其实就是正数 N - k + 1个结点
 * 因为是链表，所以我们要找到 正数 N - k 个结点
 * 1. 先遍历链表，遍历链表的同时 ，对 k的值减1
 *  这样在遍历完链表后， k = k-n
 * 2. 此时 k 会有三种情况
 *  1. k==0 --> 表示要删除的结点正好是头结点
 *  2. k > 0 --> 表示没有倒数第k个结点
 *  3. k < 0 --> 有倒数第k个结点
 * 3. 如果倒数第k个结点存在，则从头结点出发，遍历链表，直到 k == 0
 *  ==> k-n ==> 0 --> 说明需要走 n-k步，此时指针指向的结点正好是 要删除的结点的前一个
 * -------------------------------------------------------------------------
 * 也可以使用快慢双指针 ==> 快指针先走 K 步 ---> K递减为0 ==> 此时 快指针 距离 链表末尾还有 N - K步
 * 快慢指针同时出发，当快指针到达链表末尾时，慢指针正好指向要删除的结点的前一个==> 进行删除操作
 */
class DelLastKthNodeImpl {

    /**
     * 单链表删除
     */
    Node delLastKThNode(Node head,int k ) {
        if(k ==0 || head.next == null) {
           return head.next;
        }
        Node p = head;
        while(p.next != null) {
            p = p.next;
            k--;
        }
        if(k == 0 ){
            // 删除头结点
            return head.next.next;
        }else if ( k > 0 ) {
            // 不存在k节点
            return head.next;
        } else {
            p = head;
            while( k != 0) {
                p = p.next;
                k++;
            }
            p.next = p.next.next;
            return head.next;
        }

    }

}



